package class31To40;

import java.util.Stack;


public class SortStack {

    public static void main(String[] args) {
        Stack<Integer> st = new Stack<>();
        st.push(3);
        st.push(5);
        st.push(1);
        st.push(5);
        st.push(2);
        sortStack(st);
        while (!st.isEmpty()) {
            System.out.println(st.pop());
        }
    }
    // 对栈中元素进行排序
    private static void sortStack(Stack<Integer> st) {
        int deep = getDeep(st);
        while (deep > 0) {
            int max = getMaxNum(st, deep);
            int times = getMaxTimes(st, deep, max);
            downMax(st, deep, max, times);
            deep -= times;
        }
    }
    // 将最大元素沉底
    private static void downMax(Stack<Integer> st, int deep, int max, int times) {
        if (deep == 0) {
            for (int i = 0; i < times; i++) {
                st.push(max);
            }
            return;
        }
        int num = st.pop();
        downMax(st, deep - 1, max, times);
        if (num != max) {
            st.push(num);
        }
    }
    // 得到栈中最大元素个数
    private static int getMaxTimes(Stack<Integer> st, int deep, int max) {
        if (deep == 0) {
            return 0;
        }
        int num = st.pop();
        int maxTimes = getMaxTimes(st, deep - 1, max) + (num == max ? 1 : 0);
        st.push(num);
        return maxTimes;
    }
    // 得到栈中最大元素
    private static int getMaxNum(Stack<Integer> st, int deep) {
        if (deep == 0) {
            return Integer.MIN_VALUE;
        }
        int num = st.pop();
        int max = getMaxNum(st, deep - 1);
        max = Math.max(num, max);
        st.push(num);
        return max;
    }
    // 得到栈的深度
    private static int getDeep(Stack<Integer> st) {
        if (st.isEmpty()) {
            return 0;
        }
        int num = st.pop();
        int depth = getDeep(st) + 1;
        st.push(num);
        return depth;
    }
}
